/* 
 * File:   G6Library.h
 * Author: sergey
 *
 * Created on 10 Январь 2011 г., 20:17
 */

#ifndef G6LIBRARY_H
#define	G6LIBRARY_H

#include "LibraryInterface.h"
#include "BooleanFunction.h"
#include <vector>

#include <stdlib.h>
#include <time.h>

#include <algorithm>

#include "tbb/spin_mutex.h"
#include "tbb/mutex.h"

struct PItem{
    UInt32 f;
    UInt8 c;
    PItem(UInt32 f, UInt8 c) : f(f), c(c) {}
};


struct GParamsExample {
    enum {
        iterationsNumber = 250, // количество итераций
        maxPopulationSize = 16, // максимальный размер популяции (желательно степень двойки)
        rndPopulationSize = 8, // размер случайной популяции, которая рождается в начале каждой итерации
        minComplexity = 13, // минимальная сложность, которую ищем
        startPopulationSize = 16, // количество случайных функций в начальной популяции
        numIterRCrossoversD2 = 2, // количество r-кроссоверов в размере n / 2
        numIterHCrossoversD2 = 2, // количество h-кроссоверов
        numIterMutations = 2, // количество мутаций
        maxMutMask = 0xF, // маска максимального количества битов в мутации
        inversionsSize = 5, // количество массива инверсий
        maxBestSolution = 16, // размер массива, в котором запоминается количество лучших решений (желательно степень двойки)
        numBestSolution = 1, // количество функций, переносимых из массива "лучших решений"
        killAllNumIter = 250, // количество итераций, через которое убиваем всех кроме killAllNum
        killAllNum = 1 // смотри killAllNumIter
    };
    static const int inversionsByteNum[]; // число инверсируемых бит
    static const int inversionsMaxNum[]; // число инверсий
};

template <typename GParams>
struct GParamsAlgsExample {
    inline static UInt32 getIndividual(const int i) {
        return (((UInt32)rand()) << 1) ^ ((UInt32)rand() & 1);
    }
    inline static UInt32 getRandomFunction() {
        return (((UInt32)rand()) << 1) ^ ((UInt32)rand() & 1);
    }
    inline static UInt32 getIndFromPopulation(const std::vector<PItem> &population) {
        return population[rand() & (population.size() - 1)].f;
    }
    inline static bool doKillIt(const UInt32 j, const UInt32 size) {
        // очень странная строчка, так как остаток от деления заменен
        // на побитовую конъюнкцию
        return j > (rand() % size);
    }

};

inline bool operator < (const PItem &a, const PItem &b) {
    if (a.c == b.c) {
        return a.f < b.f;
    } else return a.c < b.c;
}

template <typename PreLib,
          typename GParams,
          template <typename G>
               class GParamsAlgs >
class G6Library:public LibraryInterface {
public:
    G6Library(PreLib &preLib, UInt32 lpsize) {
        this->preLib = &preLib;
        bestSolutions.reserve(GParams::maxBestSolution);
        lpSolutions.resize(lpsize);
        
        srand ( time(NULL) );
    }
    ~G6Library() {
        
    }

    typedef LibraryInfo<6> LibInfo;

    inline void pushFunction(std::vector<PItem> &population, const UInt32 f, const UInt8 c) {
        PItem newi = PItem(f,c);
        typename std::vector<PItem>::iterator i =
                 std::lower_bound(population.begin(), population.end(), newi);
        if (i == population.end() || i->f != f) {
            population.insert(i, newi);
        }
    }

    inline void setf(std::vector<PItem> &population, const UInt64 f) {
        this->f = f;
        this->f1 = f >> 32;
        this->f2 = f & 0xFFFFffff;
        
        pushFunction(population, f1, minimize(f1));
        pushFunction(population, f2, minimize(f2));
        pushFunction(population, f1 ^ f2, minimize(f1 ^ f2));
        pushFunction(population, 0, minimize(0));
    }

    inline UInt8 minimize(const UInt32 f3) {
        UInt8 res = 0, c;
        
        preLib->get(f1 ^ f3, c);
        res += c;
        
        preLib->get(f2 ^ f3, c);
        res += c;
        
        preLib->get(f3, c);
        res += c;

        return res;
    }
    
    inline void get(const UInt64 f, UInt8 &c, const UInt32 lp) {
        tbb::spin_mutex::scoped_lock l;
        std::vector<PItem> population, newPopulation;
        population.reserve(GParams::maxPopulationSize);
        newPopulation.reserve(2 * GParams::maxPopulationSize);

        UInt32 f3, m, ft1, ft2;
        int i, j, t, jj;
        setf(population, f);

        // формирование начальной популяции
        for(i = GParams::startPopulationSize; i--; ) {
            f3 = GParamsAlgs<GParams>::getIndividual(i);
            pushFunction(population, f3, minimize(f3));
        }
        
        if (bestSolutions.size() > GParams::numBestSolution) {
            for(i = GParams::numBestSolution; i--; ) {
                j = rand() % bestSolutions.size();
                pushFunction(population, bestSolutions[j], minimize(bestSolutions[j]));
            }
        } else {
            for(i = bestSolutions.size(); i--; ) {
                pushFunction(population, bestSolutions[i], minimize(bestSolutions[i]));
            }
        }

        // пихаем lp-функции в начальную популяцию
        l.acquire(lpMutex);
        pushFunction(population, lpSolutions[lp], minimize(lpSolutions[lp]));
        pushFunction(population, lpSolutions[lp - 1 >= 0 ? lp - 1 : lp + 1], minimize(lpSolutions[lp - 1 >= 0 ? lp - 1 : lp + 1]));
        i = rand() % lpSolutions.size();
        pushFunction(population, lpSolutions[i], minimize(lpSolutions[i]));
        l.release();
        
        newPopulation = population;
        
        size_t killAll = 0;
        
        for(i = GParams::iterationsNumber; i--; ) {
            if (killAll >= GParams::killAllNumIter) {
                killAll = 0;
                population.erase(population.begin() + GParams::killAllNum, population.end());
                
                // формирование начальной популяции
                for(j = GParams::startPopulationSize; j--; ) {
                    f3 = GParamsAlgs<GParams>::getIndividual(j);
                    pushFunction(population, f3, minimize(f3));
                }
                newPopulation.clear();
            } killAll++;
        
            // создание случайных функций в количестве rndPopulationSize
            for(j = GParams::rndPopulationSize; j--; ) {
                f3 = GParamsAlgs<GParams>::getRandomFunction();
                pushFunction(newPopulation, f3, minimize(f3));
            }

            // создание случайных r-кроссоверов в размере 2 * numRCrossoversD2
            for(j = GParams::numIterRCrossoversD2; j--; ) {
                m = GParamsAlgs<GParams>::getRandomFunction();
                ft1 = GParamsAlgs<GParams>::getIndFromPopulation(population);
                ft2 = GParamsAlgs<GParams>::getIndFromPopulation(population);
                f3 = (ft1 & m) ^ (ft2 & (~m));
                pushFunction(newPopulation, f3, minimize(f3));
                f3 = (ft1 & (~m)) ^ (ft2 & m);
                pushFunction(newPopulation, f3, minimize(f3));
            }

            // создание случайных h-кроссоверов в размере 2 * numHCrossoversD2
            for(j = GParams::numIterHCrossoversD2; j--; ) {
                ft1 = GParamsAlgs<GParams>::getIndFromPopulation(population);
                ft2 = GParamsAlgs<GParams>::getIndFromPopulation(population);
                f3 = (ft1 >> 16) ^ ((ft2 & 0xFFFF) << 16);
                pushFunction(newPopulation, f3, minimize(f3));
                f3 = (ft2 >> 16) ^ ((ft1 & 0xFFFF) << 16);
                pushFunction(newPopulation, f3, minimize(f3));
            }

            // мутации
            for(j = GParams::numIterMutations; j--; ) {
                f3 = GParamsAlgs<GParams>::getIndFromPopulation(population);
                for(t = rand() & GParams::maxMutMask; t--; )
                    f3 = f3 ^ (static_cast<UInt32>(1) << (rand() & 0x1F));
                pushFunction(newPopulation, f3, minimize(f3));
            }

            // инверсии
            for(j = GParams::inversionsSize; j--; ) {
                for(jj = GParams::inversionsMaxNum[j]; jj--; ) {
                    f3 = GParamsAlgs<GParams>::getIndFromPopulation(population);
                    for(t = GParams::inversionsByteNum[j]; t--; )
                        f3 = f3 ^ (static_cast<UInt32>(1) << (rand() & 0x1F));
                    pushFunction(newPopulation, f3, minimize(f3));
                }
            }

            // при необходимости дописываем новую популяцию особями старой
            // популяции до нужного размера
            while(newPopulation.size() <= GParams::maxPopulationSize) {
                f3 = GParamsAlgs<GParams>::getIndFromPopulation(population);
                pushFunction(newPopulation, f3, minimize(f3));
            }

            // убиваем некоторых особей до тех пор, пока не получим нужный размер
            while(newPopulation.size() > GParams::maxPopulationSize) {
                j = rand() % newPopulation.size();
                if (GParamsAlgs<GParams>::doKillIt(j,newPopulation.size())) {
                    newPopulation.erase(newPopulation.begin() + j);
                }
            }

            population = newPopulation;
        }
        
        if (bestSolutions.size() < GParams::maxBestSolution) {
            l.acquire(bsMutex);
            bestSolutions.push_back(population[0].f);
            l.release();
        } else {
            l.acquire(bsMutex);
            bestSolutions[rand() % bestSolutions.size()] = population[0].f;
            l.release();
        }
        
        c = population[0].c;
        l.acquire(lpMutex);
        lpSolutions[lp] = population[0].f;
        l.release();
    }
private:
    PreLib *preLib;
    UInt64 f;
    UInt32 f1, f2;
    std::vector<UInt64> bestSolutions;
    std::vector<UInt32> lpSolutions;
    tbb::spin_mutex bsMutex, lpMutex;
};

#endif	/* G6LIBRARY_H */
